package org.raymond.iworks.study.basic.structure.linkedlist;

/**
 * @author raymond
 * @version V1.0
 * @Description:
 * 构建环形链表的思路:
 * 1,先创建第一个节点,让front指向该节点,并形成环形
 * 2,每创建一个新的节点,就把新的节点加入已有的环形链表中
 * 遍历环形链表:
 * 1,先用一个辅助指针tail,指向front节点
 * 2,然后通过一个while循环遍历链表即可,结束标志:tail.next=first
 */
public class CircleSingleLinkedList {
    private BoyNode first;

    public void add(int num){
       if(num<=0) return;

       // 指向单向循环链表中的最后一个节点,以便接入新的节点
       BoyNode cur = null;
       for(int i=1; i<=num; i++){
           BoyNode boy = new BoyNode(i);
           if(i==1){
               first = boy;
               // 一个节点也要循环连接起来
               first.next=first;
               cur = first;
           } else {
               cur.next=boy;
               boy.next=first;
               // last指针移动到新加入的最后一个节点
               cur = boy;
           }
       }
    }

    public boolean isEmpty(){
        boolean isEmpty = first==null;
        if(isEmpty){
            System.err.println("循环链表为空");
        }
        return isEmpty;
    }

    public void list(){
        if(isEmpty()){
            return;
        }
        BoyNode cur = first;
        while(true){
            System.out.printf("节点编号:%d\n", cur.no);
            // 说明已经遍历完毕
            if(cur.next==first){
                break;
            }
            cur = cur.next;
        }
    }

    /**
     * 根据用户的输入,计算出节点出圈的顺序
     * @param startNo 从哪里开始
     * @param count 表示数几下
     * @param num 表示链中有多少节点
     */
    public void count(int startNo, int count, int num){
        if(first==null || startNo<1 || startNo>num){
            System.err.println("参数输入有误");
            return;
        }
        BoyNode tmp = first;
        while (true) {
            // tmp移动到最后,这样tmp就在first的前一个节点了
            if(tmp.next==first){
                break;
            }
            tmp = tmp.next;
        }
        // 报数前,先让first和tmp移动k-1次,因为要从k开始报数
        for(int j=0; j<startNo-1; j++){
            first = first.next;
            tmp = tmp.next;
        }
        // 报数时,让first和tmp指针同时移动m-1次,然后出圈,因为要报数到m后出圈
        // 循环操作,直到圈中只剩一个节点
        while(true){
            if(tmp==first){
                break;
            }
            // 让first和tmp指针同时移动count-1次
            for(int j=0; j<count-1; j++){
                first = first.next;
                tmp = tmp.next;
            }
            // 此时,first指向的节点,就是要出圈的节点
            System.out.printf("编号:%d出圈\n", first.no);
            // 将first指向的节点出圈
            first = first.next;
            tmp.next=first;
        }

        System.out.printf("编号:%d 留在圈中\n", first.no);
    }
}
